이진 탐색 트리란
이진 탐색과 연결 리스트를 결합한 자료구조의 일종이다.
다음과 같은 속성을 갖는다.
- 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
- 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
- 이 경우, 중복된 값을 가질 수 없다. (위 정의가 변경된다면 가능)
- 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.
이진탐색트리를 순회할 때는 중위순회 방식을 사용한다. 이렇게 하면 이진탐색트리 내에 있는 모든 값들을 정렬된 순서대로 읽을 수 있다.
복잡도
탐색, 삽입, 삭제의 계산 복잡도는 모두 O(h) 이다. 트리의 높이에 의해 수행 시간이 결정된다.
그러나 균형이 맞지 않는 이진탐색트리의 경우 시간복잡도가 O(N) 이 된다. 이를 해결하기 위해 AVL Tree 가 제안되었다.